LeetCode Hot100

哈希

• 两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], i);
  }
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i]) && map.get(target - nums[i]) !== i) {
      return [i, map.get(target - nums[i])];
    }
  }
};

• 字母异位词

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  let map = new Map();
  for (let str of strs) {
    if (map.has(str.split("").sort().join(""))) {
      map.get(str.split("").sort().join("")).push(str);
    } else {
      map.set(str.split("").sort().join(""), [str]);
    }
  }
  return Array.from(map.values());
};

• 最长连续序列(使用set和动态规划)

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  let set = new Set(nums);
  let result = 0;
  for (let num of nums) {
    if (!set.has(num - 1)) {
      let current = num;
      let count = 1;
      while (set.has(current + 1)) {
        current++;
        count++;
      }
      result = Math.max(result, count);
    }
  }
  return result;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length == 0) {
    return 0;
  }
  let dp = [];
  let result = 1;
  dp[0] = 1;
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    dp[i] = 1;
    if (nums[i] == nums[i - 1]) {
      dp[i] = dp[i - 1];
    }
    if (nums[i] == nums[i - 1] + 1) {
      dp[i] = dp[i - 1] + 1;
    }
    result = Math.max(result, dp[i]);
  }
  return result;
};

双指针

• 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let a = 0;
  let b = 0;
  while (a < nums.length) {
    if (nums[a] !== 0) {
      nums[b] = nums[a];
      b++;
    }
    a++;
  }
  while (b < nums.length) {
    nums[b] = 0;
    b++;
  }
};

• 盛最多水的容器(从两端往中间移动短板，因为多少水是由短板决定的，移动长板并不能改善)

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let result = 0;
  let left = 0;
  let right = height.length - 1;
  while (left < right) {
    result = Math.max(
      result,
      (right - left) * Math.min(height[left], height[right])
    );
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return result;
};

• 三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let result = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 2; i++) {
    if (i === 0 || nums[i] !== nums[i - 1]) {
      let sum = 0 - nums[i];
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        if (nums[left] + nums[right] === sum) {
          result.push([nums[i], nums[left], nums[right]]);
          left++;
          right--;
          while (left < right && nums[left] === nums[left - 1]) left++; // 跳过重复元素
          while (left < right && nums[right] === nums[right + 1]) right--; // 跳过重复元素
        } else if (nums[left] + nums[right] < sum) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return result;
};

• 接雨水(双指针，类似于打擂，永远是强者在台上)

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let result = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        result += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        result += rightMax - height[right];
      }
      right--;
    }
  }
  return result;
};

滑动窗口

• 无重复字符的最长字串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let max = 0;
  let start = 0;
  let map = new Map();
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      start = Math.max(start, map.get(s[i]) + 1);
    }
    max = Math.max(max, i - start + 1);
    map.set(s[i], i);
  }
  return max;
};

• 找到字符串中所有的字母异位词

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  if (s.length < p.length) return [];
  let result = [];
  let pMap = new Array(26).fill(0);
  let sMap = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    sMap[s.charCodeAt(i) - 97]++;
    pMap[p.charCodeAt(i) - 97]++;
  }
  for (let i = 0; i <= s.length - p.length; i++) {
    if (sMap.join("") === pMap.join("")) result.push(i);
    sMap[s.charCodeAt(i) - 97]--;
    sMap[s.charCodeAt(i + p.length) - 97]++;
  }
  return result;
};

子串

• 和为k的子数组(前缀和优化)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let result = 0;
  let sum = 0;
  let map = new Map();
  map.set(0, 1);
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    result += map.get(sum - k) || 0;
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return result;
};

• 滑动窗口最大值(单调队列-双端队列)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const q = [];
  const result = [];
  for (let i = 0; i < k; i++) {
    while (q.length && nums[q[q.length - 1]] <= nums[i]) {
      q.pop();
    }
    q.push(i);
  }
  result.push(nums[q[0]]);

  for (let i = k; i < nums.length; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
    while (q[0] <= i - k) {
      q.shift();
    }
    result.push(nums[q[0]]);
  }
  return result;
};

普通数组

• 最大子数组和(类似于dp，当和小于0的时候就丢弃)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = nums[0];
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (sum < 0) {
      sum = 0;
    }
    sum += nums[i];
    max = Math.max(max, sum);
  }
  return max;
};

• 合并区间（排序）

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < intervals.length - 1; i++) {
    if (intervals[i][1] >= intervals[i + 1][0]) {
      intervals[i][1] = Math.max(intervals[i][1], intervals[i + 1][1]);
      intervals.splice(i + 1, 1);
      i--;
    }
  }
  return intervals;
};

• 轮转数组(注意处理k大于数组长度的情况)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k = k % nums.length;
  nums.unshift(...nums.slice(nums.length - k));
  nums.splice(nums.length - k, k);
};

• 除自身以外数组的乘积(前缀乘积和后缀乘积)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let pre = new Array(nums.length).fill(1);
  let post = new Array(nums.length).fill(1);
  let result = [];
  pre[0] = nums[0];
  for (let i = 1; i < nums.length; i++) {
    pre[i] = pre[i - 1] * nums[i];
  }
  post[nums.length - 1] = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    post[i] = post[i + 1] * nums[i];
  }
  for (let i = 0; i < nums.length; i++) {
    result.push(
      i === 0
        ? post[i + 1]
        : i === nums.length - 1
        ? pre[i - 1]
        : pre[i - 1] * post[i + 1]
    );
  }
  return result;
};

• 空间复杂度为o(1) ，利用输出数组作为后缀乘积

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let post = new Array(nums.length).fill(1);
  post[nums.length - 1] = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    post[i] = post[i + 1] * nums[i];
  }
  let pre = 1;
  for (let i = 0; i < nums.length - 1; i++) {
    post[i] = post[i + 1] * pre;
    pre *= nums[i];
  }
  post[nums.length - 1] = pre;
  return post;
};

• 缺失的第一个正数(将现有数组想办法当成hash表)

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 1 || nums[i] > nums.length) {
      nums[i] = Infinity;
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (
      nums[i] < Infinity &&
      nums[i] > -Infinity &&
      nums[Math.abs(nums[i]) - 1] > 0
    ) {
      nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return nums.length + 1;
};

矩阵

• 矩阵置零

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  let m = matrix.length;
  let n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    if (matrix[i].includes(0)) {
      for (let j = 0; j < n; j++) {
        if (matrix[i][j] !== 0) {
          matrix[i][j] = "x";
        } else {
          for (let k = 0; k < m; k++) {
            if (matrix[k][j] !== 0) {
              matrix[k][j] = "x";
            }
          }
        }
      }
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === "x") {
        matrix[i][j] = 0;
      }
    }
  }
};

• 旋转图像(先镜像再反转等同于旋转90°)

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
  let n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n / 2; j++) {
      [matrix[i][j], matrix[i][n - 1 - j]] = [
        matrix[i][n - 1 - j],
        matrix[i][j],
      ];
    }
  }
};

• 搜索二维矩阵(对行进行二分)

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let m = matrix.length;
  let n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] <= target && matrix[i][n - 1] >= target) {
      let left = 0;
      let right = n - 1;
      while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (matrix[i][mid] === target) {
          return true;
        } else if (matrix[i][mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
  }
  return false;
};

链表

• 相交链表(先记录两个链表的长度)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  let lengthA = 0;
  let lengthB = 0;
  let p1 = headA;
  while (p1) {
    lengthA++;
    p1 = p1.next;
  }
  let p2 = headB;
  while (p2) {
    lengthB++;
    p2 = p2.next;
  }
  if (lengthA > lengthB) {
    [headA, headB] = [headB, headA];
    [lengthA, lengthB] = [lengthB, lengthA];
  }
  let diff = lengthB - lengthA;
  while (diff) {
    headB = headB.next;
    diff--;
  }
  while (headA !== headB) {
    headA = headA.next;
    headB = headB.next;
  }
  return headA;
};

• 反转链表(prev current next 一开始current指向头，三个一起移动)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null;
  let current = head;
  while (current) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
};

• 回文链表（双指针找到中点，然后把后半部分反转）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  let p1 = head;
  let p2 = head;
  while (p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
  }
  let prev = null;
  let current = p1;
  while (current) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  while (prev) {
    if (prev.val !== head.val) return false;
    prev = prev.next;
    head = head.next;
  }
  return true;
};

• 环形链表(快慢指针)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) return true;
  }
  return false;
};

• 环形链表II(关键是知道当快慢指针相遇时，再有一个指针从头开始走，会和慢指针相遇在pos处)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let p1 = head;
  let p2 = head;
  let pos = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      while (pos !== p1) {
        pos = pos.next;
        p1 = p1.next;
      }
      return pos;
    }
  }
  return null;
};

• 合并两个有序列表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  let p1 = list1;
  let p2 = list2;
  let newList = new ListNode(0);
  let head = newList;
  while (p1 && p2) {
    if (p1.val < p2.val) {
      head.next = p1;
      p1 = p1.next;
    } else {
      head.next = p2;
      p2 = p2.next;
    }
    head = head.next;
  }
  while (p1) {
    head.next = p1;
    p1 = p1.next;
    head = head.next;
  }
  while (p2) {
    head.next = p2;
    p2 = p2.next;
    head = head.next;
  }
  return newList.next;
};

• 两数相加

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let newList = new ListNode(0);
  let head = newList;
  let cnt = 0;
  while (l1 && l2) {
    let sum = l1.val + l2.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l1 = l1.next;
    l2 = l2.next;
  }
  while (l1) {
    let sum = l1.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l1 = l1.next;
  }
  while (l2) {
    let sum = l2.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l2 = l2.next;
  }
  if (cnt) {
    head.next = new ListNode(cnt);
  }
  return newList.next;
};

• 删除链表的倒数第N个节点(双指针，第二个指针先走n步)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let p1 = head;
  let p2 = head;
  while (n > 0) {
    p1 = p1.next;
    n--;
  }
  while (p1 && p1.next) {
    p1 = p1.next;
    p2 = p2.next;
  }
  if (p1) {
    p2.next = p2.next.next;
  } else {
    head = head.next;
  }
  return head;
};

• 两两交换链表中的节点(设置一个前驱节点)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  if (!head || !head.next) return head;
  let newList = new ListNode(0);
  newList.next = head;
  let prev = newList;
  let p1 = head;
  let p2 = head.next;
  while (p1 && p2) {
    prev.next = p2;
    p1.next = p2.next;
    p2.next = p1;
    prev = p1;
    p1 = p1.next;
    p2 = p1 ? p1.next : null;
  }
  return newList.next;
};

• 随机链表的复制（使用递归 题解）

var copyRandomList = function(head, cachedNode = new Map()) {
    if (head === null) {
        return null;
    }
    if (!cachedNode.has(head)) {
        cachedNode.set(head, {val: head.val}), Object.assign(cachedNode.get(head), {next: copyRandomList(head.next, cachedNode), random: copyRandomList(head.random, cachedNode)})
    }
    return cachedNode.get(head);
}

• 排序链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  let p1 = head;
  let arr = [];
  while (p1) {
    arr.push(p1.val);
    p1 = p1.next;
  }
  arr.sort((a, b) => a - b);
  let ans = new ListNode(0);
  let p2 = ans;
  while (arr.length) {
    p2.next = new ListNode(arr.shift());
    p2 = p2.next;
  }
  return ans.next;
};

• LRU缓存（双向链表+哈希表）

function ListNode(key, val) {
  this.key = key;
  this.val = val;
  this.next = null;
  this.prev = null;
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.cache = new Map();
  this.head = new ListNode(null, null);
  this.tail = new ListNode(null, null);
  this.head.next = this.tail;
  this.tail.prev = this.head;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    const node = this.cache.get(key);
    this.moveToFront(node);
    this.cache.set(key, node);
    return node.val;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    const node = this.cache.get(key);
    node.val = value;
    this.moveToFront(node);
    this.cache.set(key, node);
  } else {
    if (this.cache.size === this.capacity) {
      this.cache.delete(this.tail.prev.key);
      this.removeLast();
    }
    const node = new ListNode(key, value);
    this.addToFront(node);
    this.cache.set(key, node);
  }
};

LRUCache.prototype.addToFront = function (node) {
  node.next = this.head.next;
  this.head.next.prev = node;
  this.head.next = node;
  node.prev = this.head;
};
LRUCache.prototype.moveToFront = function (node) {
  this.removeNode(node);
  this.addToFront(node);
};
LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
};
LRUCache.prototype.removeLast = function () {
  this.removeNode(this.tail.prev);
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

二叉树

• 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let result = [];
  inOrder(root, result);
  return result;
};
const inOrder = function (node, result) {
  if (!node) return;
  inOrder(node.left, result);
  result.push(node.val);
  inOrder(node.right, result);
};

• 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  let left = maxDepth(root.left);
  let right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

• 翻转二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
};

• 对称二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  if (!root) return true;
  return isMirror(root.left, root.right);
};
var isMirror = function (t1, t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (
    t1.val === t2.val &&
    isMirror(t1.left, t2.right) &&
    isMirror(t1.right, t2.left)
  );
};

• 二叉树的直径（在求深度的过程中维护一个左+右的最大值）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let ans = 0;
  const maxDepth = (root) => {
    if (!root) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    ans = Math.max(ans, left + right);
    return Math.max(left, right) + 1;
  };
  maxDepth(root);
  return ans;
};

• 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  let result = [];
  let queue = [root];
  while (queue.length) {
    let currentQueue = [];
    let currentLevel = queue.length;
    for (let i = 0; i < currentLevel; i++) {
      let current = queue.shift();
      currentQueue.push(current.val);
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }
    result.push(currentQueue);
  }
  return result;
};

• 将有序数组转换为二叉搜索树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  if (nums.length === 0) return null;
  const mid = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
};

• 验证二叉搜索树（注意左边所有数字都要小于根）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  const helper = (node, min, max) => {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return (
      helper(node.left, min, node.val) && helper(node.right, node.val, max)
    );
  };
  return helper(root, -Infinity, Infinity);
};

• 二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let arr = [];
  function inOrder(node) {
    if (!node) return null;
    inOrder(node.left);
    arr.push(node.val);
    inOrder(node.right);
  }
  inOrder(root);
  arr.sort((a, b) => a - b);
  return arr[k - 1];
};

//使用非递归方式进行中序遍历
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    k--;
    if (k === 0) return root.val;
    root = root.right;
  }
};

• 二叉树的右视图(先层次遍历，然后取每一个的最后一位)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  const arr = levelOrder(root);
  let ans = [];
  arr.map((item) => {
    ans.push(item[item.length - 1]);
  });
  return ans;
};

var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  let currentLevel = [];
  while (queue.length) {
    let length = queue.length;
    for (let i = 0; i < length; i++) {
      let node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(currentLevel);
    currentLevel = [];
  }
  return res;
};

• 二叉树展开为链表（前序的顺序展开为链表，使用递归后序遍历）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  let prev = null;
  let preOrder = (node) => {
    if (!node) return;
    preOrder(node.right);
    preOrder(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  };
  preOrder(root);
};

• 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if (preorder.length === 0) return null;
  let mid = inorder.indexOf(preorder[0]);
  let root = new TreeNode(preorder[0]);
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return root;
};

• 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (!left) return right;
  if (!right) return left;
  return root;
};

图论

• 岛屿数量（dfs次数）

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let m = grid.length;
  let n = grid[0].length;
  let count = 0;
  let xx = [-1, 0, 1, 0];
  let yy = [0, 1, 0, -1];
  const dfs = (grid, i, j) => {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== "1") {
      return;
    }
    grid[i][j] = "2";
    for (let k = 0; k < 4; k++) {
      dfs(grid, i + xx[k], j + yy[k]);
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(grid, i, j);
      }
    }
  }

  return count;
};

• 腐烂的橘子

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  let queue = [];
  let fresh = 0;
  let time = 0;
  let m = grid.length;
  let n = grid[0].length;
  let move = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      if (grid[i][j] === 1) fresh++;
    }
  }
  while (queue.length) {
    let size = queue.length;
    for (i = 0; i < size; i++) {
      let [x, y] = queue.shift();
      for (let [dx, dy] of move) {
        let xx = x + dx;
        let yy = y + dy;
        if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] === 1) {
          grid[xx][yy] = 2;
          fresh--;
          queue.push([xx, yy]);
        }
      }
    }
    time++;
  }
  return fresh ? -1 : Math.max(0, time - 1);
};

• 课程表（bfs，记录入度和每个课程的后续课程）

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  let inDegree = new Array(numCourses).fill(0);
  let map = new Map();
  let count = 0;
  for (let i = 0; i < prerequisites.length; i++) {
    if (map.has(prerequisites[i][1])) {
      map.get(prerequisites[i][1]).push(prerequisites[i][0]);
    } else {
      map.set(prerequisites[i][1], [prerequisites[i][0]]);
    }
    inDegree[prerequisites[i][0]]++;
  }
  let queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  while (queue.length) {
    let current = queue.shift();
    count++;
    let children = map.get(current);
    children &&
      children.map((child) => {
        inDegree[child]--;
        if (inDegree[child] === 0) {
          queue.push(child);
        }
      });
  }
  return count === numCourses;
};

回溯

• 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let res = [];
  if (!nums.length) return res;
  const dfs = (path) => {
    if (path.length === nums.length) {
      res.push(path);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (!path.includes(nums[i])) {
        dfs(path.concat(nums[i]));
      }
    }
  };
  dfs([]);
  return res;
};

• 子集（重做）

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  let result = [];
  let dfs = (start, path) => {
    result.push(path);
    for (let i = start; i < nums.length; i++) {
      dfs(i + 1, [...path, nums[i]]);
    }
  };
  dfs(0, []);
  return result;
};

• 电话号码的字母组合

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) return [];
  let map = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
  let result = [];

  const dfs = (index, str) => {
    if (index === digits.length) {
      result.push(str);
      return;
    }
    for (let i = 0; i < map[digits[index]].length; i++) {
      dfs(index + 1, str + map[digits[index]][i]);
    }
  };
  dfs(0, "");
  return result;
};

• 组合总和（先找数再去重）

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  let set = new Set();
  let result = [];
  const dfs = (path, sum) => {
    if (sum > target) return;
    if (sum === target) {
      path.sort((a, b) => a - b);
      set.add(JSON.stringify(path));
      return;
    }
    for (let i = 0; i < candidates.length; i++) {
      dfs(path.concat(candidates[i]), sum + candidates[i]);
    }
  };
  dfs([], 0);
  result = Array.from(set).map((item) => JSON.parse(item));
  return result;
};

• 括号生成(左右括号数量)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  if (n <= 0) return [];
  let result = [];
  const dfs = (left, right, str) => {
    if (!left && !right) {
      result.push(str);
      return;
    }
    if (left === right) {
      dfs(left - 1, right, str + "(");
    } else if (left < right) {
      if (left > 0) dfs(left - 1, right, str + "(");
      dfs(left, right - 1, str + ")");
    }
  };
  dfs(n, n, "");
  return result;
};

• 单词搜索

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let m = board.length;
  let n = board[0].length;
  let move = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  let ans = false;
  let visited = Array(m)
    .fill(0)
    .map(() => Array(n).fill(false));

  const dfs = (x, y, word) => {
    if (board[x][y] !== word[0]) return;
    if (word.length === 1) {
      ans = true;
      return;
    }
    visited[x][y] = true;
    for (let i = 0; i < 4; i++) {
      let xx = x + move[i][0];
      let yy = y + move[i][1];
      if (xx >= 0 && yy >= 0 && xx < m && yy < n && !visited[xx][yy]) {
        dfs(xx, yy, word.substring(1));
        visited[xx][yy] = false;
      }
    }
  };
  for (let i = 0; i < m; i++) {
    let index = board[i].indexOf(word[0]);
    while (index !== -1 && !ans) {
      dfs(i, index, word);
      visited[i][index] = false;
      index = board[i].indexOf(word[0], index + 1);
    }
  }
  return ans;
};

二分

• 搜索插入位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

• 搜索二维矩阵（二维二分，注意 边界）

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) {
    return false;
  }
  if (
    target < matrix[0][0] ||
    target > matrix[matrix.length - 1][matrix[0].length - 1]
  )
    return false;
  let m = matrix.length;
  let n = matrix[0].length;

  const getRow = () => {
    let l = 0;
    let r = m - 1;
    while (l <= r) {
      let mid = Math.floor((l + r) / 2);
      if (matrix[mid][0] <= target && matrix[mid][n - 1] >= target) {
        return mid;
      } else if (matrix[mid][0] > target) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  const row = getRow();
  let l = 0;
  let r = n - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (matrix[row][mid] === target) {
      return true;
    } else if (matrix[row][mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return matrix[row][l] === target;
};

• 在排序数组中查找元素的第一个和最后一个位置(取巧，找target+0.5和-0.5)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  let target1 = target - 0.5;
  let target2 = target + 0.5;

  const find = (target) => {
    let l = 0,
      r = nums.length - 1;
    while (l <= r) {
      let mid = Math.floor((l + r) / 2);
      if (nums[mid] < target) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return l;
  };
  let left = find(target1);
  let right = find(target2);
  if (nums[left] === target && nums[right - 1] === target) {
    return [left, right - 1];
  } else {
    return [-1, -1];
  }
};

• 搜索旋转排序数组

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] === target) return mid;
    if (nums[l] <= nums[mid]) {
      if (nums[l] <= target && target < nums[mid]) r = mid - 1;
      else l = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[r]) l = mid + 1;
      else r = mid - 1;
    }
  }
  return -1;
};

• 寻找旋转排序数组中的最小值

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    if (l === r) {
      return nums[l];
    }
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] < nums[r]) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return nums[l];
};

栈

• 括号匹配

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  let map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "{" || s[i] === "[") {
      stack.push(s[i]);
    } else {
      let last = stack.pop();
      if (s[i] !== map[last]) {
        return false;
      }
    }
  }
  return stack.length === 0;
};

• 最小栈

var MinStack = function () {
  this.stack = [];
  this.minStack = [];
};

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val);
  if (
    this.minStack.length === 0 ||
    val <= this.minStack[this.minStack.length - 1]
  ) {
    this.minStack.push(val);
  } else {
    this.minStack.push(this.minStack[this.minStack.length - 1]);
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.minStack[this.minStack.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

• 字符串编码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let queue = [];
  let ans = "";
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== "]") {
      queue.push(s[i]);
    } else {
      let current = queue.pop();
      let temp = "";
      let count = 0;
      let times = 0;
      while (current !== "[") {
        temp = current + temp;
        current = queue.pop();
      }
      while (queue.length > 0 && !isNaN(queue[queue.length - 1])) {
        count = count + Math.pow(10, times) * parseInt(queue.pop());
        times++;
      }
      queue.push(temp.repeat(count));
    }
  }
  return queue.join("");
};

• 每日温度

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  let ans = new Array(temperatures.length).fill(0);
  let queue = [];
  for (let i = 0; i < temperatures.length; i++) {
    if (!queue.length) {
      queue.push({ index: i, value: temperatures[i] });
    } else {
      let top = queue[queue.length - 1];
      if (temperatures[i] < top.value) {
        queue.push({ index: i, value: temperatures[i] });
      } else {
        while (
          queue.length &&
          temperatures[i] > queue[queue.length - 1].value
        ) {
          let top = queue.pop();
          ans[top.index] = i - top.index;
        }
        queue.push({ index: i, value: temperatures[i] });
      }
    }
  }
  return ans;
};

贪心

• 买卖股票的最佳时机

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min = Infinity;
    let max = 0;
    for(let i=0;i<prices.length;i++){
        if(prices[i]<min){
            min = prices[i];
        }
        max = Math.max(max,prices[i]-min);
    }
    return max;
};

• 跳跃游戏（倒序遍历）

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length<=1) return true;
    let len = 1;
    for(let i = nums.length-2;i>0;i--){
        if(nums[i]>=len){
            len = 1;
        }else{
            len++;
        }
    }
    if(nums[0]>=len) return true;
    return false;
};

• 跳跃游戏II

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let ans = 0;
    let maxPos = 0;
    let end = 0;
    for(let i=0;i<nums.length-1;i++){
        maxPos = Math.max(maxPos,i+nums[i]);
        if(end===i){
            end = maxPos; 
            ans++;
        }
    }
    return ans;
};

• 划分字母区间

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
    let start = 0;
    let end = 0;
    let ans = [];
    let last = [];
    for(let i = 0;i<s.length;i++){
        last[s[i]] = i;
    }
    for(let i=0;i<s.length;i++){
        end = Math.max(end,last[s[i]]);
        if(i===end){
            ans.push(end-start+1);
            start = end+1;
        }
    }
    return ans;
};

• 爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

• 杨辉三角

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  const result = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let j = 0; j <= i; j++) {
      if (j === 0 || j === i) {
        row.push(1);
      } else {
        row.push(result[i - 1][j - 1] + result[i - 1][j]);
      }
    }
    result.push(row);
  }
  return result;
};

• 打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  if (nums.length < 2) {
    return nums[0];
  }
  let dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[nums.length - 1];
};

• 完全平方数

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  let dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let min = Infinity;
    for (let j = 1; j * j <= i; j++) {
      min = Math.min(min, dp[i - j * j]);
    }
    dp[i] = min + 1;
  }
  return dp[n];
};

技巧

• 只出现一次的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ans = nums[0];
  for (let i = 1; i < nums.length; i++) {
    ans ^= nums[i];
  }
  return ans;
};

• 多数元素

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let ans = 0;
    let count = 0;
    for(let i=0;i<nums.length;i++){
        if(count===0){
            ans = nums[i];
        }
        if(ans===nums[i]){
            count++;
        }else{
            count--;
        }
    }
    return ans;
};